home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / hashtable.h < prev    next >
C/C++ Source or Header  |  1997-05-28  |  33KB  |  1,071 lines
  1. /*
  2.  * Copyright (c) 1996
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  *
  13.  *
  14.  * Copyright (c) 1994
  15.  * Hewlett-Packard Company
  16.  *
  17.  * Permission to use, copy, modify, distribute and sell this software
  18.  * and its documentation for any purpose is hereby granted without fee,
  19.  * provided that the above copyright notice appear in all copies and
  20.  * that both that copyright notice and this permission notice appear
  21.  * in supporting documentation.  Hewlett-Packard Company makes no
  22.  * representations about the suitability of this software for any
  23.  * purpose.  It is provided "as is" without express or implied warranty.
  24.  *
  25.  * Exception Handling:
  26.  * Copyright (c) 1997
  27.  * Mark of the Unicorn, Inc.
  28.  *
  29.  * Permission to use, copy, modify, distribute and sell this software
  30.  * and its documentation for any purpose is hereby granted without fee,
  31.  * provided that the above copyright notice appear in all copies and
  32.  * that both that copyright notice and this permission notice appear
  33.  * in supporting documentation.  Mark of the Unicorn makes no
  34.  * representations about the suitability of this software for any
  35.  * purpose.  It is provided "as is" without express or implied warranty.
  36.  *
  37.  * Adaptation:
  38.  * Copyright (c) 1997
  39.  * Moscow Center for SPARC Technology
  40.  *
  41.  * Permission to use, copy, modify, distribute and sell this software
  42.  * and its documentation for any purpose is hereby granted without fee,
  43.  * provided that the above copyright notice appear in all copies and
  44.  * that both that copyright notice and this permission notice appear
  45.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  46.  * representations about the suitability of this software for any
  47.  * purpose.  It is provided "as is" without express or implied warranty.
  48.  *
  49.  */
  50.  
  51.  
  52. #ifndef __SGI_STL_HASHTABLE_H
  53. #define __SGI_STL_HASHTABLE_H
  54.  
  55. // Hashtable class, used to implement the hashed associative containers
  56. // hash_set, hash_map, hash_multiset, and hash_multimap.
  57.  
  58.  
  59. #include <stdlib.h>
  60. #include <stddef.h>
  61. # ifndef __SGI_STL_ALGO_H
  62. #  include <algo.h>
  63. # endif
  64. # ifndef __SGI_STL_VECTOR_H
  65. #  include <vector.h>
  66. # endif
  67.  
  68. # if defined ( __STL_USE_ABBREVS )
  69. #  define __hashtable_iterator         _hT__It
  70. #  define __hashtable_const_iterator   _hT__cIt
  71. #  define __hashtable_node             _hT__N
  72. #  define __hashtable_base             _hT__B
  73. #  define hashtable                    _h__T
  74. # endif
  75.  
  76. __BEGIN_STL_NAMESPACE
  77.  
  78. template <class Key> struct hash { };
  79.  
  80. inline size_t __stl_hash_string(const char* s)
  81. {
  82.   unsigned long h = 0; 
  83.   for ( ; *s; ++s)
  84.     h = 5*h + *s;
  85.   
  86.   return size_t(h);
  87. }
  88.  
  89. struct hash<char*>
  90. {
  91.   size_t operator()(const char* s) const { return __stl_hash_string(s); }
  92. };
  93.  
  94. struct hash<const char*>
  95. {
  96.   size_t operator()(const char* s) const { return __stl_hash_string(s); }
  97. };
  98.  
  99. struct hash<char> {
  100.   size_t operator()(char x) const { return x; }
  101. };
  102. struct hash<unsigned char> {
  103.   size_t operator()(unsigned char x) const { return x; }
  104. };
  105. struct hash<signed char> {
  106.   size_t operator()(unsigned char x) const { return x; }
  107. };
  108. struct hash<short> {
  109.   size_t operator()(short x) const { return x; }
  110. };
  111. struct hash<unsigned short> {
  112.   size_t operator()(unsigned short x) const { return x; }
  113. };
  114. struct hash<int> {
  115.   size_t operator()(int x) const { return x; }
  116. };
  117. struct hash<unsigned int> {
  118.   size_t operator()(unsigned int x) const { return x; }
  119. };
  120. struct hash<long> {
  121.   size_t operator()(long x) const { return x; }
  122. };
  123. struct hash<unsigned long> {
  124.   size_t operator()(unsigned long x) const { return x; }
  125. };
  126.  
  127. template <class Value>
  128. struct __hashtable_node
  129. {
  130.   typedef __hashtable_node<Value> self;
  131.   self* next;
  132.   Value val;
  133. };  
  134.  
  135. template <class Value, class Key, class HashFcn,
  136.           class ExtractKey, class EqualKey , __DFL_TYPE_PARAM(Alloc,alloc)>
  137. class hashtable;
  138.  
  139. template <class Value, class Key, class HashFcn,
  140.           class ExtractKey, class EqualKey, class Alloc>
  141. struct __hashtable_iterator;
  142.  
  143. template <class Value, class Key, class HashFcn,
  144.           class ExtractKey, class EqualKey, class Alloc>
  145. struct __hashtable_const_iterator;
  146.  
  147. template <class Value, class Key, class HashFcn,
  148.           class ExtractKey, class EqualKey, class Alloc>
  149. struct __hashtable_iterator 
  150. # if defined ( __STL_DEBUG )
  151.     : public __safe_base 
  152. # endif
  153. {
  154.   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
  155.           hash_table;
  156.   typedef __hashtable_iterator<Value, Key, HashFcn, 
  157.                                ExtractKey, EqualKey, Alloc>
  158.           iterator;
  159.   typedef __hashtable_const_iterator<Value, Key, HashFcn, 
  160.                                      ExtractKey, EqualKey, Alloc>
  161.           const_iterator;
  162.   typedef __hashtable_node<Value> node;
  163.   typedef size_t size_type;
  164.   typedef Value& reference;
  165.   typedef const Value& const_reference;
  166.  
  167.   node* cur;
  168.   hash_table* ht;
  169.  
  170. # if defined ( __STL_DEBUG )
  171.   const node* get_iterator() const { return cur; }
  172.   const hash_table* owner() const { return (const hash_table*)__safe_base::owner(); }
  173.   __hashtable_iterator(node* n, hash_table* tab) : 
  174.       __safe_base(tab), cur(n), ht(tab) {}
  175.   __hashtable_iterator() : __safe_base(0) {}
  176. # else
  177.   __hashtable_iterator(node* n, hash_table* tab) : cur(n), ht(tab) {}
  178.   __hashtable_iterator() {}
  179. # endif
  180.   reference operator*() const { 
  181.         __stl_verbose_assert(valid() && cur!=0,__STL_MSG_NOT_DEREFERENCEABLE);
  182.         return cur->val; 
  183.   }
  184.   iterator& operator++();
  185.   iterator operator++(int);
  186.   bool operator==(const iterator& it) const { 
  187.       __stl_debug_check(__check_same_owner(*this,it));
  188.       return cur == it.cur; 
  189.   }
  190.   bool operator!=(const iterator& it) const { 
  191.       __stl_debug_check(__check_same_owner(*this,it));
  192.       return cur != it.cur; 
  193.   }
  194. };
  195.  
  196.  
  197. template <class Value, class Key, class HashFcn,
  198.           class ExtractKey, class EqualKey, class Alloc>
  199. struct __hashtable_const_iterator 
  200. # if defined ( __STL_DEBUG )
  201.     : public __safe_base 
  202. # endif
  203. {
  204.   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
  205.           hash_table;
  206.   typedef __hashtable_iterator<Value, Key, HashFcn, 
  207.      ExtractKey, EqualKey, Alloc> iterator;
  208.   typedef __hashtable_const_iterator<Value, Key, HashFcn, 
  209.      ExtractKey, EqualKey, Alloc> const_iterator;
  210.   typedef __hashtable_node<Value> node;
  211.   typedef size_t size_type;
  212.   typedef Value& reference;
  213.   typedef const Value& const_reference;
  214.  
  215.   const node* cur;
  216.   const hash_table* ht;
  217.  
  218. # if defined ( __STL_DEBUG )
  219.   const hash_table* owner() const { return (const hash_table*)__safe_base::owner(); }
  220.   const node* get_iterator() const { return cur; }
  221.   __hashtable_const_iterator(const node* n, const hash_table* tab)
  222.     : __safe_base(tab), cur(n), ht(tab) {}
  223.   __hashtable_const_iterator() : __safe_base(0) {}
  224.   __hashtable_const_iterator(const iterator& it) : __safe_base(it), cur(it.cur), ht(it.ht) {}
  225. # else
  226.   __hashtable_const_iterator(const node* n, const hash_table* tab)
  227.     : cur(n), ht(tab) {}
  228.   __hashtable_const_iterator() {}
  229.   __hashtable_const_iterator(const iterator& it) : cur(it.cur), ht(it.ht) {}
  230. # endif
  231.  
  232.   const_reference operator*() const { 
  233.       __stl_verbose_assert(valid() && cur!=0,__STL_MSG_NOT_DEREFERENCEABLE);
  234.       return cur->val; 
  235.   }
  236.   const_iterator& operator++();
  237.   const_iterator operator++(int);
  238.   bool operator==(const const_iterator& it) const { 
  239.       __stl_debug_check(__check_same_owner(*this,it));
  240.       return cur == it.cur; 
  241.   }
  242.   bool operator!=(const const_iterator& it) const { 
  243.       __stl_debug_check(__check_same_owner(*this,it));
  244.       return cur != it.cur; 
  245.   }
  246. };
  247.  
  248. // Note: assumes long is at least 32 bits.
  249. // fbp: try to avoid intances in every module
  250. enum { __stl_num_primes = 28 };
  251.  
  252. #if ( __STL_STATIC_TEMPLATE_DATA > 0 )
  253. #  define __stl_prime_list __stl_prime<false>::list_
  254.    template <bool dummy>
  255.    struct __stl_prime {
  256.    public:
  257.        static const unsigned long list_[];
  258.    };
  259.    template <bool dummy>
  260.    const unsigned long __stl_prime<dummy>::list_[] =
  261. #  else
  262. #  if ( __STL_WEAK_ATTRIBUTE > 0 )
  263.       extern const unsigned long __stl_prime_list[__stl_num_primes] __attribute__((weak)) =
  264. #  else
  265.       // give up
  266.       static const unsigned long __stl_prime_list[__stl_num_primes] =
  267. #  endif /* __STL_WEAK_ATTRIBUTE */
  268. #endif /* __STL_STATIC_TEMPLATE_DATA */
  269. {
  270.   53,         97,         193,       389,       769,
  271.   1543,       3079,       6151,      12289,     24593,
  272.   49157,      98317,      196613,    393241,    786433,
  273.   1572869,    3145739,    6291469,   12582917,  25165843,
  274.   50331653,   100663319,  201326611, 402653189, 805306457, 
  275.   1610612741, 3221225473, 4294967291
  276. };
  277.  
  278. inline unsigned long __stl_next_prime(unsigned long n)
  279. {
  280.   const unsigned long* last = __stl_prime_list + __stl_num_primes;
  281.   const unsigned long* pos = lower_bound((const unsigned long*)__stl_prime_list, last, n);
  282.   return pos == last ? *(last - 1) : *pos;
  283. }
  284.  
  285. template <class Value, class Alloc>
  286. class __hashtable_base 
  287. # if defined ( __STL_DEBUG )
  288.  : public __safe_base
  289. # endif
  290. {
  291. private:
  292.     typedef Value value_type;
  293.     typedef size_t size_type;
  294.     typedef __hashtable_node<Value> node;
  295.     typedef simple_alloc<node, Alloc> node_allocator;
  296. public:    // These are public to get around restriction on protected access
  297.     __vector__<node*, Alloc> buckets;
  298.     size_type num_elements;
  299. protected:
  300.     void clear();
  301.  
  302.     node* new_node(const value_type& obj)
  303.     {
  304.             node* n = node_allocator::allocate();
  305.             __TRY {
  306.                 construct(&(n->val), obj);
  307.             }
  308. #  if defined (__STL_USE_EXCEPTIONS)
  309.             catch(...) {
  310.                 node_allocator::deallocate(n);
  311.                 throw;
  312.             }
  313. #  endif
  314.             n->next = 0;
  315.             return n;
  316.     }
  317.     
  318.     void delete_node(node* n)
  319.     {
  320.             destroy(&(n->val));
  321.             node_allocator::deallocate(n);
  322.     }
  323.  
  324.     void copy_from(const __hashtable_base<Value,Alloc>& ht);
  325.     
  326. public:    // These are public to get around restriction on protected access
  327.     __hashtable_base() : num_elements(0) { }
  328. //    __hashtable_base(size_type n) : num_elements(0) {}
  329.     ~__hashtable_base() { clear(); __stl_debug_do(invalidate()); }
  330. };
  331.  
  332.  
  333. template <class Value, class Key, class HashFcn,
  334.           class ExtractKey, class EqualKey,
  335.           class Alloc>
  336. class hashtable : protected __hashtable_base<Value, Alloc> 
  337. {
  338.   typedef __hashtable_base<Value, Alloc> super;
  339.   typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> self;
  340. public:
  341.   typedef Key key_type;
  342.   typedef Value value_type;
  343.   typedef HashFcn hasher;
  344.   typedef EqualKey key_equal;
  345.  
  346.   typedef size_t            size_type;
  347.   typedef ptrdiff_t         difference_type;
  348.   typedef value_type*       pointer;
  349.   typedef const value_type* const_pointer;
  350.   typedef value_type&       reference;
  351.   typedef const value_type& const_reference;
  352.  
  353.   hasher hash_funct() const { return hashfun; }
  354.   key_equal key_eq() const { return equals; }
  355.  
  356. private:
  357.   hasher hashfun;
  358.   key_equal equals;
  359.   ExtractKey get_key;
  360.  
  361.   typedef __hashtable_node<Value> node;
  362.   typedef simple_alloc<node, Alloc> node_allocator;
  363.  
  364. public:
  365.   typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;
  366.   typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey,Alloc> const_iterator;
  367.   friend struct
  368.   __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
  369.   friend struct
  370.   __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>;
  371.  
  372. public:
  373.   hashtable(size_type n,
  374.             const HashFcn&    hf,
  375.             const EqualKey&   eql,
  376.             const ExtractKey& ext)
  377.       : hashfun(hf), equals(eql), get_key(ext) {
  378.         __stl_debug_do(safe_init(this));
  379.         initialize_buckets(n);
  380.     }
  381.  
  382.   hashtable(size_type n,
  383.             const HashFcn&    hf,
  384.             const EqualKey&   eql)
  385.       : hashfun(hf), equals(eql), get_key(ExtractKey()) {
  386.         __stl_debug_do(safe_init(this));
  387.         initialize_buckets(n);
  388.     }
  389.  
  390.   hashtable(const self& ht)
  391.     : hashfun(ht.hashfun), equals(ht.equals), get_key(ht.get_key) {
  392.         __stl_debug_do(safe_init(this));
  393.         copy_from(ht);
  394.   }
  395.  
  396.   self& operator= (const self& ht)
  397.   {
  398.     if (&ht != this) {
  399.       hashfun = ht.hashfun;
  400.       equals = ht.equals;
  401.       get_key = ht.get_key;
  402.       clear();
  403.       buckets.clear();
  404.       copy_from(ht);
  405.     }
  406.     return *this;
  407.   }
  408.  
  409.   ~hashtable() {}
  410.  
  411.   size_type size() const { return num_elements; }
  412.   size_type max_size() const { return size_type(-1); }
  413.   bool empty() const { return size() == 0; }
  414.  
  415.   void swap(self& ht)
  416.   {
  417.     __STL_NAMESPACE::swap(hashfun, ht.hashfun);
  418.     __STL_NAMESPACE::swap(equals, ht.equals);
  419.     __STL_NAMESPACE::swap(get_key, ht.get_key);
  420.     buckets.swap(ht.buckets);
  421.     __STL_NAMESPACE::swap(num_elements, ht.num_elements);
  422.     __stl_debug_do(swap_owners(ht));
  423.   }
  424.  
  425.   iterator begin()
  426.   { 
  427.     for (size_type n = 0; n < buckets.size(); ++n)
  428.       if (buckets[n])
  429.         return iterator(buckets[n], this);
  430.     return end();
  431.   }
  432.  
  433.   iterator end() { return iterator((node*)0, this); }
  434.  
  435.   const_iterator begin() const
  436.   {
  437.     for (size_type n = 0; n < buckets.size(); ++n)
  438.       if (buckets[n])
  439.         return const_iterator(buckets[n], this);
  440.     return end();
  441.   }
  442.  
  443.   const_iterator end() const { return const_iterator((node*)0, this); }
  444.  
  445.   friend bool operator== (const self&,const self&);
  446.  
  447. public:
  448.  
  449.   size_type bucket_count() const { return buckets.size(); }
  450.  
  451.   size_type max_bucket_count() const
  452.     { return __stl_prime_list[__stl_num_primes - 1]; } 
  453.  
  454.   size_type elems_in_bucket(size_type bucket) const
  455.   {
  456.     size_type result = 0;
  457.     for (node* cur = buckets[bucket]; cur; cur = cur->next)
  458.       result += 1;
  459.     return result;
  460.   }
  461.  
  462.   pair<iterator, bool> insert_unique(const value_type& obj)
  463.   {
  464.     resize(num_elements + 1);
  465.     return insert_unique_noresize(obj);
  466.   }
  467.  
  468.   iterator insert_equal(const value_type& obj)
  469.   {
  470.     resize(num_elements + 1);
  471.     return insert_equal_noresize(obj);
  472.   }
  473.  
  474.   pair<iterator, bool> insert_unique_noresize(const value_type& obj);
  475.   iterator insert_equal_noresize(const value_type& obj);
  476.  
  477.   void insert_unique(const value_type* f, const value_type* l)
  478.   {
  479.     size_type n = l - f;
  480.     resize(num_elements + n);
  481.     for ( ; n > 0; --n)
  482.       insert_unique_noresize(*f++);
  483.   }
  484.  
  485.   void insert_equal(const value_type* f, const value_type* l)
  486.   {
  487.     size_type n = l - f;
  488.     resize(num_elements + n);
  489.     for ( ; n > 0; --n)
  490.       insert_equal_noresize(*f++);
  491.   }
  492.  
  493.  void insert_unique(const_iterator f, const_iterator l)
  494.   {
  495.     size_type n = 0;
  496.     distance(f, l, n);
  497.     resize(num_elements + n);
  498.     for ( ; n > 0; --n)
  499.       insert_unique_noresize(*f++);
  500.   }
  501.  
  502.   void insert_equal(const_iterator f, const_iterator l)
  503.   {
  504.     size_type n = 0;
  505.     distance(f, l, n);
  506.     resize(num_elements + n);
  507.     for ( ; n > 0; --n)
  508.       insert_equal_noresize(*f++);
  509.   }
  510.  
  511.   reference find_or_insert(const value_type& obj);
  512.  
  513.   iterator find(const key_type& key) 
  514.   {
  515.     size_type n = bkt_num_key(key);
  516.     node* first;
  517.     for ( first = buckets[n];
  518.           first && !equals(get_key(first->val), key);
  519.           first = first->next)
  520.       {}
  521.     return iterator(first, this);
  522.   } 
  523.  
  524.   const_iterator find(const key_type& key) const
  525.   {
  526.     size_type n = bkt_num_key(key);
  527.     const node* first;
  528.     for ( first = buckets[n];
  529.           first && !equals(get_key(first->val), key);
  530.           first = first->next)
  531.       {}
  532.     return const_iterator(first, this);
  533.   } 
  534.  
  535.   size_type count(const key_type& key) const
  536.   {
  537.     const size_type n = bkt_num_key(key);
  538.     size_type result = 0;
  539.  
  540.     for (const node* cur = buckets[n]; cur; cur = cur->next)
  541.       if (equals(get_key(cur->val), key))
  542.         ++result;
  543.     return result;
  544.   }
  545.  
  546.   pair<iterator, iterator> equal_range(const key_type& key);
  547.   pair<const_iterator, const_iterator> equal_range(const key_type& key) const;
  548.  
  549.   size_type erase(const key_type& key);
  550.   void erase(const iterator& it);
  551.   void erase(iterator first, iterator last);
  552.  
  553.   void erase(const const_iterator& it);
  554.   void erase(const_iterator first, const_iterator last);
  555.  
  556.   void resize(size_type num_elements_hint);
  557.   void clear() { super::clear(); __stl_debug_do(invalidate_all()); }
  558. # if defined (__STL_DEBUG)
  559.     void invalidate_node(node* it) { 
  560.         __invalidate_iterator(this,it,iterator());
  561.     }
  562.     void delete_node(node* n){ invalidate_node(n); super::delete_node(n);}
  563. # endif
  564. private:
  565.     size_type next_size(size_type n) const { return __stl_next_prime(n); }
  566.  
  567.     void initialize_buckets(size_type n)
  568.     {
  569.         const size_type n_buckets = next_size(n);
  570.         buckets.reserve(n_buckets);
  571.         buckets.insert(buckets.end(), n_buckets, (node*) 0);
  572.         num_elements = 0;
  573.     }
  574.     size_type bkt_num_key(const key_type& key) const{
  575.         return bkt_num_key(key, buckets.size());
  576.     }
  577.  
  578.     size_type bkt_num(const value_type& obj) const {
  579.         return bkt_num_key(get_key(obj));
  580.     }
  581.  
  582.     size_type bkt_num_key(const key_type& key, size_t n) const {
  583.         return hashfun(key) % n;
  584.     }
  585.  
  586.     size_type bkt_num(const value_type& obj, size_t n) const {
  587.         return bkt_num_key(get_key(obj), n);
  588.     }
  589.     void erase_bucket(const size_type n, node* first, node* last);
  590.     void erase_bucket(const size_type n, node* last);
  591. };
  592.  
  593. // fbp: these defines are for outline methods definitions.
  594. // needed to definitions to be portable. Should not be used in method bodies.
  595.  
  596. # if defined ( __STL_NESTED_TYPE_PARAM_BUG )
  597. #  define __difference_type__ ptrdiff_t
  598. #  define __size_type__       size_t
  599. #  define __value_type__      Value
  600. #  define __key_type__        Key
  601. #  define __node__            __hashtable_node<Value>
  602. #  define __reference__       Value&
  603. # else
  604. #  define __difference_type__  hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::difference_type
  605. #  define __size_type__        hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::size_type
  606. #  define __value_type__       hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::value_type
  607. #  define __key_type__         hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::key_type
  608. #  define __node__             hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node
  609. #  define __reference__        hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::reference
  610. # endif
  611.  
  612. template <class Value, class Key, class HashFcn,
  613.     class ExtractKey, class EqualKey, class Alloc>
  614. INLINE_LOOP __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
  615. __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
  616. {
  617.   const node* old = cur;
  618.   __stl_verbose_assert(old!=0,__STL_MSG_INVALID_ADVANCE);
  619.   cur = cur->next;
  620.   if (!cur) {
  621.     size_type bucket = ht->bkt_num(old->val);
  622.     while (!cur && ++bucket < ht->buckets.size())
  623.       cur = ht->buckets[bucket];
  624.   }
  625.   return *this;
  626. }
  627.  
  628. template <class Value, class Key, class HashFcn,
  629.           class ExtractKey, class EqualKey, class Alloc>
  630. inline __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
  631. __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
  632. {
  633.   iterator tmp = *this;
  634.   ++*this;
  635.   return tmp;
  636. }
  637.  
  638. template <class Value, class Key, class HashFcn,
  639.           class ExtractKey, class EqualKey, class Alloc>
  640. INLINE_LOOP __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&
  641. __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++()
  642. {
  643.   const node* old = cur;
  644.   __stl_verbose_assert(old!=0,__STL_MSG_INVALID_ADVANCE);
  645.   cur = cur->next;
  646.   if (!cur) {
  647.     size_type bucket = ht->bkt_num(old->val);
  648.     while (!cur && ++bucket < ht->buckets.size())
  649.       cur = ht->buckets[bucket];
  650.   }
  651.   return *this;
  652. }
  653.  
  654. template <class Value, class Key, class HashFcn,
  655.           class ExtractKey, class EqualKey, class Alloc>
  656. inline __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>
  657. __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::operator++(int)
  658. {
  659.   const_iterator tmp = *this;
  660.   ++*this;
  661.   return tmp;
  662. }
  663.  
  664. template <class Value, class Key, class HashFcn,
  665.           class ExtractKey, class EqualKey, class Alloc>
  666. inline forward_iterator_tag
  667. iterator_category(const __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
  668. {
  669.   return forward_iterator_tag();
  670. }
  671.  
  672. template <class Value, class Key, class HashFcn,
  673.           class ExtractKey, class EqualKey, class Alloc>
  674. inline Value* 
  675. value_type(const __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
  676. {
  677.   return (Value*) 0;
  678. }
  679.  
  680. template <class Value, class Key, class HashFcn,
  681.           class ExtractKey, class EqualKey, class Alloc>
  682. inline ptrdiff_t*
  683. distance_type(const __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
  684. {
  685.   return (ptrdiff_t*) 0;
  686. }
  687.  
  688. template <class Value, class Key, class HashFcn,
  689.           class ExtractKey, class EqualKey, class Alloc>
  690. inline forward_iterator_tag
  691. iterator_category(const __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
  692. {
  693.   return forward_iterator_tag();
  694. }
  695.  
  696. template <class Value, class Key, class HashFcn,
  697.           class ExtractKey, class EqualKey, class Alloc>
  698. inline Value* 
  699. value_type(const __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
  700. {
  701.   return (Value*) 0;
  702. }
  703.  
  704. template <class Value, class Key, class HashFcn,
  705.           class ExtractKey, class EqualKey, class Alloc>
  706. inline ptrdiff_t*
  707. distance_type(const __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>&)
  708. {
  709.   return (ptrdiff_t*) 0;
  710. }
  711.  
  712.  
  713.  
  714. template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc>
  715. bool operator==(const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht1,
  716.                 const hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& ht2)
  717. {
  718.   typedef typename hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::node node;
  719.   if (ht1.buckets.size() != ht2.buckets.size())
  720.     return false;
  721.   for (int n = 0; n < ht1.buckets.size(); ++n) {
  722.     node* cur1 = ht1.buckets[n];
  723.     node* cur2 = ht2.buckets[n];
  724.     for ( ; cur1 && cur2 && cur1->val == cur2->val;
  725.           cur1 = cur1->next, cur2 = cur2->next)
  726.       {}
  727.     if (cur1 || cur2)
  728.       return false;
  729.   }
  730.   return true;
  731. }  
  732.  
  733.  
  734. template <class Value, class Key, class HashFcn,
  735.           class ExtractKey, class EqualKey, class Alloc>
  736. pair<__hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>, bool> 
  737. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_unique_noresize(const __value_type__& obj)
  738. {
  739.   const size_type n = bkt_num(obj);
  740.   node* first = buckets[n];
  741.  
  742.   for (node* cur = first; cur; cur = cur->next) 
  743.     if (equals(get_key(cur->val), get_key(obj)))
  744.       return pair<iterator, bool>(iterator(cur, this), false);
  745.  
  746.   node* tmp = new_node(obj);
  747.   tmp->next = first;
  748.   buckets[n] = tmp;
  749.   ++num_elements;
  750.   return pair<iterator, bool>(iterator(tmp, this), true);
  751. }
  752.  
  753. template <class Value, class Key, class HashFcn,
  754.           class ExtractKey, class EqualKey, class Alloc>
  755. __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> 
  756. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::insert_equal_noresize(const __value_type__& obj)
  757. {
  758.   const size_type n = bkt_num(obj);
  759.   node* first = buckets[n];
  760.  
  761.   for (node* cur = first; cur; cur = cur->next) 
  762.     if (equals(get_key(cur->val), get_key(obj))) {
  763.       node* tmp = new_node(obj);
  764.       tmp->next = cur->next;
  765.       cur->next = tmp;
  766.       ++num_elements;
  767.       return iterator(tmp, this);
  768.     }
  769.  
  770.   node* tmp = new_node(obj);
  771.   tmp->next = first;
  772.   buckets[n] = tmp;
  773.   ++num_elements;
  774.   return iterator(tmp, this);
  775. }
  776.  
  777. template <class Value, class Key, class HashFcn,
  778.           class ExtractKey, class EqualKey, class Alloc>
  779. __reference__ 
  780. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::find_or_insert(const __value_type__& obj)
  781. {
  782.   resize(num_elements + 1);
  783.  
  784.   size_type n = bkt_num(obj);
  785.   node* first = buckets[n];
  786.  
  787.   for (node* cur = first; cur; cur = cur->next)
  788.     if (equals(get_key(cur->val), get_key(obj)))
  789.       return cur->val;
  790.  
  791.   node* tmp = new_node(obj);
  792.   tmp->next = first;
  793.   buckets[n] = tmp;
  794.   ++num_elements;
  795.   return tmp->val;
  796. }
  797.  
  798. template <class Value, class Key, class HashFcn,
  799.           class ExtractKey, class EqualKey, class Alloc>
  800. pair<__hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>,
  801.      __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> > 
  802. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key)
  803. {
  804.   typedef pair<iterator, iterator> pii;
  805.   const size_type n = bkt_num_key(key);
  806.  
  807.   for (node* first = buckets[n]; first; first = first->next) {
  808.     if (equals(get_key(first->val), key)) {
  809.       for (node* cur = first->next; cur; cur = cur->next)
  810.         if (!equals(get_key(cur->val), key))
  811.           return pii(iterator(first, this), iterator(cur, this));
  812.       for (size_type m = n + 1; m < buckets.size(); ++m)
  813.         if (buckets[m])
  814.           return pii(iterator(first, this),
  815.                      iterator(buckets[m], this));
  816.       return pii(iterator(first, this), end());
  817.     }
  818.   }
  819.   return pii(end(), end());
  820. }
  821.  
  822. template <class Value, class Key, class HashFcn,
  823.           class ExtractKey, class EqualKey, class Alloc>
  824. pair<__hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>, 
  825.      __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> > 
  826. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::equal_range(const __key_type__& key) const
  827. {
  828.   typedef pair<const_iterator, const_iterator> pii;
  829.   const size_type n = bkt_num_key(key);
  830.  
  831.   for (const node* first = buckets[n] ; first; first = first->next) {
  832.     if (equals(get_key(first->val), key)) {
  833.       for (const node* cur = first->next; cur; cur = cur->next)
  834.         if (!equals(get_key(cur->val), key))
  835.           return pii(const_iterator(first, this),
  836.                      const_iterator(cur, this));
  837.       for (size_type m = n + 1; m < buckets.size(); ++m)
  838.         if (buckets[m])
  839.           return pii(const_iterator(first, this),
  840.                      const_iterator(buckets[m], this));
  841.       return pii(const_iterator(first, this), end());
  842.     }
  843.   }
  844.   return pii(end(), end());
  845. }
  846.  
  847. template <class Value, class Key, class HashFcn,
  848.           class ExtractKey, class EqualKey, class Alloc>
  849. __size_type__ 
  850. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const __key_type__& key)
  851. {
  852.   const size_type n = bkt_num_key(key);
  853.   node* first = buckets[n];
  854.   size_type erased = 0;
  855.  
  856.   if (first) {
  857.     node* cur = first;
  858.     node* next = cur->next;
  859.     while (next) {
  860.       if (equals(get_key(next->val), key)) {
  861.         cur->next = next->next;
  862.         delete_node(next);
  863.         next = cur->next;
  864.         ++erased;
  865.       }
  866.       else {
  867.         cur = next;
  868.         next = cur->next;
  869.       }
  870.     }
  871.     if (equals(get_key(first->val), key)) {
  872.       buckets[n] = first->next;
  873.       delete_node(first);
  874.       ++erased;
  875.     }
  876.   }
  877.   num_elements -= erased;
  878.   return erased;
  879. }
  880.  
  881. template <class Value, class Key, class HashFcn,
  882.           class ExtractKey, class EqualKey, class Alloc>
  883. void 
  884. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
  885. {
  886.   __stl_verbose_assert(it.owner()==this, __STL_MSG_NOT_OWNER);
  887.   node* const p = it.cur;
  888.   if (p) {
  889.     const size_type n = bkt_num(p->val);
  890.     node* cur = buckets[n];
  891.  
  892.     if (cur == p) {
  893.       buckets[n] = cur->next;
  894.       delete_node(cur);
  895.       --num_elements;
  896.     }
  897.     else {
  898.       node* next = cur->next;
  899.       while (next) {
  900.         if (next == p) {
  901.           cur->next = next->next;
  902.           delete_node(next);
  903.           --num_elements;
  904.           break;
  905.         }
  906.         else {
  907.           cur = next;
  908.           next = cur->next;
  909.         }
  910.       }
  911.     }
  912.   }
  913. }
  914.  
  915. template <class Value, class Key, class HashFcn,
  916.           class ExtractKey, class EqualKey, class Alloc>
  917. void 
  918. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(__hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first, 
  919.                                         __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
  920. {
  921.   size_type f_bucket = first.cur ? bkt_num(first.cur->val) : buckets.size();
  922.   size_type l_bucket = last.cur ? bkt_num(last.cur->val) : buckets.size();
  923.   __stl_debug_check(__check_if_owner(this,first)&&__check_if_owner(this,last));
  924.   __stl_verbose_assert(f_bucket <= l_bucket, __STL_MSG_INVALID_RANGE);
  925.   if (first.cur == last.cur)
  926.     return;
  927.   else if (f_bucket == l_bucket)
  928.     erase_bucket(f_bucket, first.cur, last.cur);
  929.   else {
  930.     erase_bucket(f_bucket, first.cur, 0);
  931.     for (size_type n = f_bucket + 1; n < l_bucket; ++n)
  932.       erase_bucket(n, 0);
  933.     if (l_bucket != buckets.size())
  934.       erase_bucket(l_bucket, last.cur);
  935.   }
  936. }
  937.  
  938. template <class Value, class Key, class HashFcn,
  939.           class ExtractKey, class EqualKey, class Alloc>
  940. inline void
  941. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(__hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> first, 
  942.                                         __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> last)
  943. {
  944.   erase(iterator(__CONST_CAST(node*,first.cur),
  945.                  __CONST_CAST(self*,first.ht)),
  946.         iterator(__CONST_CAST(node*,last.cur),
  947.                  __CONST_CAST(self*,last.ht)));
  948. }
  949.  
  950. template <class Value, class Key, class HashFcn,
  951.           class ExtractKey, class EqualKey, class Alloc>
  952. inline void
  953. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase(const __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>& it)
  954. {
  955.   erase(iterator(__CONST_CAST(node*,it.cur),
  956.                  __CONST_CAST(self*,it.ht)));
  957. }
  958.  
  959. template <class Value, class Key, class HashFcn,
  960.           class ExtractKey, class EqualKey, class Alloc>
  961. void 
  962. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::resize(__size_type__ num_elements_hint)
  963. {
  964.     const size_type old_n = buckets.size();
  965.     if (num_elements_hint > old_n) {
  966.         const size_type n = next_size(num_elements_hint);
  967.         if (n > old_n) {
  968.             __vector__<node*, Alloc> tmp(n, (node*) 0);
  969.             for (size_type bucket = 0; bucket < old_n; ++bucket) {
  970.                 node* first = buckets[bucket];
  971.                 while (first) {
  972.                     size_type new_bucket = bkt_num(first->val, n);
  973.                     buckets[bucket] = first->next;
  974.                     first->next = tmp[new_bucket];
  975.                     tmp[new_bucket] = first;
  976.                     first = buckets[bucket];                    
  977.                 }
  978.             }
  979.             buckets.clear();
  980.             buckets.swap(tmp);
  981.         }
  982.     }
  983. }
  984.  
  985.  
  986. template <class Value, class Key, class HashFcn,
  987.           class ExtractKey, class EqualKey, class Alloc>
  988. void 
  989. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n, 
  990.                                              __hashtable_node<Value>* first, 
  991.                                              __hashtable_node<Value>* last)
  992. {
  993.   node* cur = buckets[n];
  994.   if (cur == first)
  995.     erase_bucket(n, last);
  996.   else {
  997.     node* next;
  998.     for (next = cur->next; next != first; cur = next, next = cur->next)
  999.       ;
  1000.     while (next) {
  1001.       cur->next = next->next;
  1002.       delete_node(next);
  1003.       next = cur->next;
  1004.       --num_elements;
  1005.     }
  1006.   }
  1007. }
  1008.  
  1009. template <class Value, class Key, class HashFcn,
  1010.           class ExtractKey, class EqualKey, class Alloc>
  1011. void 
  1012. hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc>::erase_bucket(const size_t n,
  1013.                                                             __hashtable_node<Value>* last)
  1014. {
  1015.     node* cur = buckets[n];
  1016.     while (cur != last) {
  1017.         node* next = cur->next;
  1018.         delete_node(cur);
  1019.         cur = next;
  1020.         buckets[n] = cur;
  1021.         --num_elements;
  1022.     }
  1023. }
  1024.  
  1025. template <class Value, class Alloc>
  1026. void __hashtable_base<Value, Alloc>::clear()
  1027. {
  1028.     for (size_type i = 0; i < buckets.size(); ++i) {
  1029.         node* cur = buckets[i];
  1030.         while (cur != 0) {
  1031.             node* next = cur->next;
  1032.             delete_node(cur);
  1033.             cur = next;
  1034.         }
  1035.         buckets[i] = 0;
  1036.     }
  1037.     num_elements = 0;
  1038. }
  1039.     
  1040.     
  1041. template <class Value, class Alloc>
  1042. void __hashtable_base<Value, Alloc>::copy_from(const __hashtable_base<Value, Alloc>& ht)
  1043. {
  1044.     buckets.reserve(ht.buckets.size());
  1045.     buckets.insert(buckets.end(), ht.buckets.size(), (node*) 0);
  1046.     for (size_type i = 0; i < ht.buckets.size(); ++i) {
  1047.         const node* cur = ht.buckets[i];
  1048.         if (cur) {
  1049.             node* copy = new_node(cur->val);
  1050.             buckets[i] = copy;
  1051.             ++num_elements;
  1052.             
  1053.             for (node* next = cur->next; next; cur = next, next = cur->next) {
  1054.                 copy->next = new_node(next->val);
  1055.                 ++num_elements;
  1056.                 copy = copy->next;
  1057.             }
  1058.         }
  1059.     }
  1060. }
  1061.  
  1062. # undef __difference_type__ 
  1063. # undef __size_type__       
  1064. # undef __value_type__      
  1065. # undef __key_type__        
  1066. # undef __node__            
  1067.  
  1068. __END_STL_NAMESPACE
  1069.  
  1070. #endif /* SGI_STL_HASHTABLE_H */
  1071.